package codeRandomThoughts.Test112路径总和;

import codeRandomThoughts.utils.TreeNode;


//路径总和二刷
public class Solution2 {

    int pathSum = 0;
    boolean equalTargetSum = false;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        pathSum += root.val;
        backtracking(root, targetSum);
        return equalTargetSum;
    }

    public void backtracking(TreeNode node, int targetSum) {
        //终止条件
        if (equalTargetSum) return;//剪枝
        if (node.left == null && node.right == null) {
            if (pathSum == targetSum) {
                equalTargetSum = true;
            }
            return;
        }

        //单层递归逻辑
        if (node.left != null) {
            pathSum += node.left.val;
            backtracking(node.left, targetSum);
            pathSum -= node.left.val;
        }
        if (node.right != null) {
            pathSum += node.right.val;
            backtracking(node.right, targetSum);
            pathSum -= node.right.val;
        }
    }
}
